With the advancement of Internet communications, the need for private information retrieval is increasing. For example, if company X maintains an Internet website with a complete listing of its United States and foreign patents, competitors may be interested in searching those patents when introducing competitive products or services. Without privacy from the inquirer, company X can monitor database inquiries into its patent portfolio and gain knowledge as to the identity of the patents in which the competitors are interested. Thus, it can be very important to privatize database information inquiries.
Private information retrieval ("PIR") schemes allow a user to retrieve information from an electronic storage device while maintaining the privacy of the queries from the electronic storage device. As used herein, "electronic storage device" refers to any processing system that stores information that a user at an inquiring processor may wish to retrieve. Moreover, the terms "electronic storage device" and "database" will be used interchangeably and should be understood in their broadest sense.
The least sophisticated method for performing a private information retrieval is to request a copy of the entire database. This, of course, hides the particular information sought by the inquiring processor, but requires an impractical exchange of information between the database and the inquiring processor.
Another technique for PIR requires replication of the database at alterative sites that do not communicate with one another. This replication technique is disclosed in B. Chor, O. Goldreich, et al., "Private Information Retrieval," 36th Annual IEEE Symposium On Foundations Of Computer Science, 1995, A. Ambainis, "Upper Bound On The Communication Complexity Of Private Information Retrieval," Proceedings Of 24th ICALP, Springer, Lecture Notes In Computer Science, Volume 1256, B. Chor and N. Gilboa, "Computationally Private Information Retrieval," 29th Symposium On The Theory Of Computing, and R. Ostrovsky and V. Shoup, "Private Information Storage," 29th Symposium On The Theory Of Computing. This technique requires replication of the database into two or more copies that cannot communicate with each other in order to assure privacy of user requests. However, it is not practical to maintain several copies of a database, where the copies cannot communicate with each other.
Accordingly, it is an object of the invention to improve the efficiency and effectiveness of private information retrieval schemes. It is a further object of the invention to provide private information retrieval from a database, without requiring replication of the information in several databases. It is a further object of the invention to provide private information retrieval from a database using relatively small amounts of data exchange between the database and an inquiring processor. Other objects and advantages of the invention will be apparent from the descriptions of the invention that follows.